1. Field
The present invention relates generally to databases and, more specifically, to encrypted databases in which encryption keys are withheld from the system storing the database.
2. Description of the Related Art
In certain applications, database operators remain untrusted. Users of databases often prefer not to trust the operator of the database to protect the security of their stored data. In some cases, the database resides on computing systems operated by another entity, for instance, a remote data center operated by another company, and users prefer to not trust the other entity to protect the secrecy of their data. Or in some cases, users of databases prefer to constrain which portions of, and users of, their own computing systems have access to stored data (e.g., to reduce the likelihood of an unintentional release of secure information to an untrusted environment, such as in the event of a data breach).
Some existing systems for encrypting databases expose too much information to the hosting entity. For instance, some systems allow a database server to ascertain which database entries match one another and which database entries are greater than or less than one another. Exposure of this information can weaken the underlying encryption. In some cases, the search space for encryption keys can be reduced by an attacker by knowing the ordinality of database entries, and inferences can be drawn about database entries and usage based on matching values and ordinality.
Some systems remotely store encrypted files that may be sent to client devices, and some of these systems withhold the encryption keys for the files (e.g., in zero-knowledge cloud document storage systems). Such systems are often not well suited for database storage or usage because the bandwidth and latency associated with sending a full copy of the database or other record can be intolerable for users needing a relatively fast response to a query or other database transaction.